package main

import "fmt"

/*
全排列（无重复项）
给定一个不含重复数字的数组nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]
*/

func permute(nums []int) [][]int {
	var res [][]int
	visited := map[int]bool{}
	var dfs func(path []int)
	dfs = func(path []int) {
		if len(path) == len(nums) { //如果排列满了
			//下面三行 等价于 res = append(res,append([]int{},path...))
			//temp := make([]int, len(path))
			//copy(temp, path)
			//res = append(res,temp)
			res = append(res, append([]int{}, path...))
			return
		}
		for _, n := range nums {
			if visited[n] { //如果已经存在了（为true）
				continue
			}
			path = append(path, n)
			visited[n] = true
			dfs(path)
			path = path[:len(path)-1] //将最后一个元素删除 回溯
			visited[n] = false        //将其标记为false
		}
	}
	dfs([]int{})
	return res
}

/*
//代码随想录里的
var res [][]in
func permute(nums []int) [][]int {
	res = [][]int{}
	backTrack(nums,len(nums),[]int{})
	return res
}

func backTrack(nums []int,numsLen int,path []int)  {
	if len(nums)==0{
		p:=make([]int,len(path))
		copy(p,path)
		res = append(res,p)
	}
	for i:=0;i<numsLen;i++{
		cur:=nums[i]
		path = append(path,cur)
		nums = append(nums[:i],nums[i+1:]...)//直接使用切片
		backTrack(nums,len(nums),path)
		nums = append(nums[:i],append([]int{cur},nums[i:]...)...)//回溯的时候切片也要复原，元素位置不能变
		path = path[:len(path)-1]

	}
}
*/

func main() {
	nums := []int{1, 2, 3}
	fmt.Println(permute(nums))
}
